Close
Metadata

1. Identity statement
Reference TypeConference Paper (Conference Proceedings)
Sitesibgrapi.sid.inpe.br
Holder Codeibi 8JMKD3MGPEW34M/46T9EHH
Identifier8JMKD3MGPBW34M/3JMNB5L
Repositorysid.inpe.br/sibgrapi/2015/06.19.17.45
Last Update2015:06.19.17.45.06 (UTC) administrator
Metadata Repositorysid.inpe.br/sibgrapi/2015/06.19.17.45.06
Metadata Last Update2022:06.14.00.08.05 (UTC) administrator
DOI10.1109/SIBGRAPI.2015.37
Citation KeyMalheirosWalt:2015:SiEfAp
TitleSimple and efficient approximate nearest neighbor search using spatial sorting
FormatOn-line
Year2015
Access Date2024, Apr. 28
Number of Files1
Size875 KiB
2. Context
Author1 Malheiros, Marcelo de Gomensoro
2 Walter, Marcelo
EditorPapa, Joćo Paulo
Sander, Pedro Vieira
Marroquim, Ricardo Guerra
Farrell, Ryan
e-Mail Addressmgmalheiros@gmail.com
Conference NameConference on Graphics, Patterns and Images, 28 (SIBGRAPI)
Conference LocationSalvador, BA, Brazil
Date26-29 Aug. 2015
PublisherIEEE Computer Society
Publisher CityLos Alamitos
Book TitleProceedings
Tertiary TypeFull Paper
History (UTC)2015-06-19 17:45:06 :: mgmalheiros@gmail.com -> administrator ::
2022-06-14 00:08:05 :: administrator -> :: 2015
3. Content and structure
Is the master or a copy?is the master
Content Stagecompleted
Transferable1
Version Typefinaldraft
Keywordsspatial sorting
k-nearest neighbors
parallel algorithms
data structures
AbstractFinding the nearest neighbors of a point is a highly used operation in many graphics applications. Recently, the neighborhood grid has been proposed as a new approach for this task, focused on low-dimensional spaces. In 2D, for instance, we would organize a set of points in a matrix in such a way that their x and y coordinates are at the same time sorted along rows and columns, respectively. Then, the problem of finding closest points reduces to only examining the nearby elements around a given element in the matrix. Based on this idea, we propose and evaluate novel spatial sorting strategies for the bidimensional case, providing significant performance and precision gains over previous works. We also experimentally analyze different scenarios, to establish the robustness of searching for nearest neighbors. The experiments show that for many dense point distributions, by using some of the devised algorithms, spatial sorting beats more complex and current techniques, like k-d trees and index sorting. Our main contribution is to show that spatial sorting, albeit a still scarcely researched topic, can be turned into a competitive approximate technique for the low-dimensional k-NN problem, still being simple to implement, memory efficient, robust on common cases, and highly parallelizable.
Arrangement 1urlib.net > SDLA > Fonds > SIBGRAPI 2015 > Simple and efficient...
Arrangement 2urlib.net > SDLA > Fonds > Full Index > Simple and efficient...
doc Directory Contentaccess
source Directory Contentthere are no files
agreement Directory Content
agreement.html 19/06/2015 14:45 0.7 KiB 
4. Conditions of access and use
data URLhttp://urlib.net/ibi/8JMKD3MGPBW34M/3JMNB5L
zipped data URLhttp://urlib.net/zip/8JMKD3MGPBW34M/3JMNB5L
Languageen
Target FilePID3770507.pdf
User Groupmgmalheiros@gmail.com
Visibilityshown
Update Permissionnot transferred
5. Allied materials
Mirror Repositorysid.inpe.br/banon/2001/03.30.15.38.24
Next Higher Units8JMKD3MGPBW34M/3K24PF8
8JMKD3MGPEW34M/4742MCS
Citing Item Listsid.inpe.br/sibgrapi/2015/08.03.22.49 7
sid.inpe.br/banon/2001/03.30.15.38.24 1
Host Collectionsid.inpe.br/banon/2001/03.30.15.38
6. Notes
Empty Fieldsaffiliation archivingpolicy archivist area callnumber contenttype copyholder copyright creatorhistory descriptionlevel dissemination edition electronicmailaddress group isbn issn label lineage mark nextedition notes numberofvolumes orcid organization pages parameterlist parentrepositories previousedition previouslowerunit progress project readergroup readpermission resumeid rightsholder schedulinginformation secondarydate secondarykey secondarymark secondarytype serieseditor session shorttitle sponsor subject tertiarymark type url volume


Close